package com.wang.sort;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

public class Demo23_Heap02 {
    public static class MyHeap<T> {
        private ArrayList<T> heap;
        private HashMap<T, Integer> indexMap;
        private int heapSize;
        private Comparator<? super T> comparator;

        //初始化堆结构
        public MyHeap(Comparator<? super T> comp) {
            heap = new ArrayList<>();
            indexMap = new HashMap<>();
            heapSize = 0;
            comparator =comp;
        }

        public boolean isEmpty() {
            return heapSize == 0;
        }

        public int size() {
            return heapSize;
        }

        public boolean contains(T key) {
            return indexMap.containsKey(key);
        }

        public void push(T value) {
            heap.add(value);
            indexMap.put(value, heapSize);
            heapInsert(heapSize++);
        }

        public T pop() {
            T res = heap.get(0);
            int end = heapSize - 1;
            swap(0, end);
            //同步 堆中移除 indexMap中也移除
            heap.remove(end);
            indexMap.remove(end);
            heapify(0, --heapSize);
            return res;
        }

        //动态操作大根堆中的某个value，保证大根堆的结构不变
        public void resign(T value) {
            int valueIndex = indexMap.get(value);
            //只中一个逻辑
            heapInsert(valueIndex);
            heapify(valueIndex, heapSize);
        }

        private void heapInsert(int index) {
            //通过comparator来实现比较的逻辑
            while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
                swap( index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void heapify(int index, int heapSize) {
            int left = index * 2 + 1;
            while (left < heapSize) {
                int largest = left + 1 < heapSize && comparator.compare(heap.get(left + 1), heap.get(left))  < 0? left + 1 : left;
                int alllargest = comparator.compare(heap.get(index), heap.get(largest))< 0 ? largest : index;
                if(largest == index){
                    break;
                }
                swap(largest, index);
                index = largest;
                left = index * 2 + 1;
            }
        }

        private  void swap( int i, int j) {
            T o1 = heap.get(i);
            T o2 = heap.get(j);
            //在堆中交换，在indexMap中也交换，保持一致(手动强同步)
            heap.set(i, o2);
            heap.set(j, o1);
            indexMap.put(o2, i);
            indexMap.put(o1, j);
        }

    }

}
